#include<iostream>
#include<list>
#include<unordered_map>
using namespace std;

class LRUCache0 {
    struct ListNode {
        int key;
        int val;
        ListNode* next;
        ListNode() : key(0), val(0), next(nullptr) {}
        ListNode(int k, int v) : key(k), val(v), next(nullptr) {}
        ListNode(int k, int v, ListNode* next) : key(k), val(v), next(next) {}
    };
    int _capacity;
    int _size;
    ListNode* _root;
    ListNode* _backNode;

public:
    LRUCache0(int capacity) {
        _capacity = capacity;
        _root = new ListNode(-1, -1, nullptr);
        _backNode = _root;
        _size = 0;
    }

    int get(int key) {
        if (_root == _backNode)
            return -1;
        ListNode* pcur = _root;
        while (pcur->next != nullptr) {
            if (pcur->next->key == key) {
                if (_backNode != pcur->next) {
                    _backNode->next = pcur->next;
                    pcur->next = pcur->next->next;
                    _backNode = _backNode->next;
                    _backNode->next = nullptr;
                }
                return _backNode->val;
            }
            pcur = pcur->next;
        }
        return -1;
    }

    void put(int key, int value) {
        if (_backNode != _root) {
            ListNode* pcur = _root;
            while (pcur->next != nullptr) {
                if (pcur->next->key == key) {
                    if (_backNode != pcur->next) {
                        _backNode->next = pcur->next;
                        pcur->next = pcur->next->next;
                        _backNode = _backNode->next;
                        _backNode->next = nullptr;
                    }
                    _backNode->val = value;
                    return;
                }
                pcur = pcur->next;
            }
        }
        _size++;
        _backNode->next = new ListNode(key, value, nullptr);
        _backNode = _backNode->next;
        if (_size > _capacity) {
            ListNode* delNode = _root->next;
            _root->next = delNode->next;
            delete delNode;
            --_size;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */





class LRUCache1 {
    struct DLinkedNode {
        int key, value;
        DLinkedNode* prev, * next;
        DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
        DLinkedNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head, * tail;
    int capacity;
    int size;

public:
    LRUCache1(int capacity) : capacity(capacity), size(0) {
        // dummy head/tail
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!cache.count(key)) return -1;
        DLinkedNode* node = cache[key];
        moveToTail(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToTail(node);
            return;
        }

        DLinkedNode* node = new DLinkedNode(key, value);
        cache[key] = node;
        addToTail(node);
        size++;

        if (size > capacity) {
            DLinkedNode* del = head->next; // LRU
            removeNode(del);
            cache.erase(del->key);
            delete del;
            size--;
        }
    }

private:
    void addToTail(DLinkedNode* node) {
        node->prev = tail->prev;
        node->next = tail;
        tail->prev->next = node;
        tail->prev = node;
    }

    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToTail(DLinkedNode* node) {
        removeNode(node);
        addToTail(node);
    }
};
